This invention relates to random access digital memories, and in particular to the use of interleaved memory bank selection to increase the efficiency of access to random access memory devices.
In digital computing, it is often desirable to access data sequentially from random access memory devices more rapidly than a single device, or set of devices, can respond. One solution to this problem is to partition the memory devices into sets, or "banks," of memory which may be independently selected for access and to arrange the memory addressing circuitry so that each numerically consecutive address is directed to a different memory bank. For example, the memory may be divided into four memory banks, the two least significant bits of the memory address being used to select one of the memory banks. Such an addressing system allows access to a new memory location in another memory bank to be initiated while a previously accessed memory bank completes its access cycle, thereby increasing the overall memory access speed.
A problem with the aforementioned approach is that an increment of consecutive addresses equal to the number of memory banks nevertheless accesses the same memory bank every time, and since powers of two are the most used address increments in digital computers, it is likely that the increments between consecutive addresses will frequently be equal to the number of memory banks.
An approach to solving the problem of faster interleaved memory bank selection is to use prime way interleaving. In this approach, the number of memory banks is set equal to a prime number, thereby decreasing the likelihood that power of two increments will cause sequential access to the same memory bank. However, the bank decoding logic for this approach is complex, which not only increases its expense, but tends to degrade the maximum achievable access speed performance. Moreover, consecutive address increments that are a multiple of the prime number of banks will also access the same bank consecutively.
A second approach which has been employed is to generate disorder in the selection of memory banks by using a lookup table to interleave the memory banks. That is, the memory address is provided to a read-only memory which stores a table that relates addresses to memory banks For a given memory address, a memory bank identification is stored such that the order with which the memory banks are selected changes as the memory address increases, up to some preselected memory address.
Some problems with the latter approach are that the table size is limited by the number of memory locations in the read-only memory; read-only memory devices are not fast enough to perform at the speed at which random access memory access may be required, e.g., 25 megaherts; and selection of the table in the memory has heretofore been done empirically.
Therefore, there has been a need for an improved memory bank interleaving mechanism for digital memory which increases the speed with which any sequence of memory locations may be accessed.